JZ7 斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
第一次解:递归
这里使用 HashMap 对一部分结果进行剪枝操作
import java.util.HashMap;
public class Solution {
HashMap<Integer, Integer> cache = new HashMap<>();
// F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)
public int Fibonacci(int n) {
if (n <= 1) return n; // 注意 Base 条件是 n <= 1
// 先从 cache 里面找
if (cache.get(n) != null) {
return cache.get(n);
}
int result = Fibonacci(n - 1) + Fibonacci(n - 2);
cache.put(n, result);
return result;
}
}
未剪枝是:
时间复杂度: 空间复杂度:
剪枝后:
时间复杂度: 空间复杂度:
第二次解:动态规划
//import java.util.HashMap;
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) return n;
int result = 0;
int pre = 0;
int next = 1;
for(int i = 2; i < n + 1; i++) {
result = pre + next;
pre = next;
next = result;
}
return result;
}
}